翻訳と辞書 Words near each other ・ Kargar Street ・ Kargaran ・ Kargaran Stadium ・ Kargartan ・ Kargas ・ Kargasok ・ Kargasoksky District ・ Kargat ・ Kargat River ・ Kargatsky District ・ Kargaz ・ Kargazlu ・ Kargał-Las ・ Karge meri ・ Karger Publishers ・ Karger's algorithm ・ Karges Furniture ・ Karghesh-e Olya ・ Karghond ・ Karghond Rural District ・ Kargi, Estonia ・ Kargi, Hormozgan ・ Kargi, Iran ・ Kargil ・ Kargil (disambiguation) ・ Kargil Airport ・ Kargil Chowk ・ Kargil coffin scam ・ Kargil district ・ Kargil Government High School Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Karger's algorithm ： ウィキペディア英語版 Karger's algorithm In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993. The idea of the algorithm is based on the concept of contraction of an edge $(u,\; v)$ in an undirected graph $G\; =\; (V,\; E)$. Informally speaking, the contraction of an edge merges the nodes $u$ and $v$ into one, reducing the total number of nodes of the graph by one. All other edges connecting either $u$ or $v$ are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probability. ==The global minimum cut problem == (詳細はpolynomial time by iterating over all choices of $s,t\backslash in\; V$ and solving the resulting minimum $s$-$t$ cut problem using the max-flow min-cut theorem and a polynomial time algorithm for maximum flow, such as the push-relabel algorithm, though this approach is not optimal. There is a deterministic algorithm for the global minimum cut problem with running time $O(mn+n^2\backslash log\; n)$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Karger's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.